package test;

//同时运行n台电脑的最大时间：https://leetcode.cn/problems/maximum-running-time-of-n-computers/
public class MaxRunTime {
	
	//未优化版本
	//时间复杂度:O(n*log(sum))
	
	//碎片拼接：给点1个target，一个个数n,如果数组中的元素均<=target,这种元素叫碎片
	//        那么如果 sum>=n*targrt，则target一定可以满足条件；
	
	//        如果有元素>target，那么不考虑该元素并且n--，剩余的元素继续判断
	
	//给定一个运行时间，判断n台电脑能否同时运行
	public boolean f1(int[] nums,int n,long time){
        long sum=0;
        for(int x:nums){
            if(x>time){
                n--; //直接--,多余时间无需处理，因为所以电脑运行时间只有time
            }
            else{
                sum+=x;
            }
            //为什么这里time*n不转为long,不怕溢出吗？因为time是long类型
            if(sum>=time*n){ //sum>=n*time
                return true;
            }
        }
        return false;
    }
    public long maxRunTime1(int n, int[] batteries) {
        long sum=0;
        for(int x:batteries){
            sum+=x;
        }
        //二分区间：[0,sum]
        //单调性：显然，time越小越容易同时运行
        long l=0,r=sum;
        long ret=0;
        while(l<=r){
            long mid=l+(r-l)/2;
            if(f1(batteries,n,mid)){
                l=mid+1;
                ret=mid;
            }
            else{
                r=mid-1;
            }
        }
        return ret;  
    }

    
    
	//优化版本:做一次预处理(贪心)
    //时间复杂度：O(n*log(max))
    //由于枚举区间最大值变为max(int),因此time的范围也是int
	public boolean f2(int[] nums,int n,int time){
        long sum=0;
        for(int x:nums){
            if(x>time){
                n--;
            }
            else{
                sum+=x;
            }
            //time,n均为int，因此相乘可能溢出，故将其中一个转为long类型
            if(sum>=(long)time*n){
                return true;
            }
        }
        return false;
    }
    public long maxRunTime2(int n, int[] batteries) {
        int max=0;
        long sum=0;
        for(int x:batteries){
            max=Math.max(max,x);
            sum+=x;
        }
        //电池最大为max,如果有 sum>=max*n，则说明：
        //=>所有的元素一定均是均是碎片，则只要sum>=k*n成立，k即为答案，
        //故只要找k的最大值，显然为 sum/n,因为sum/n*n=sum
        if(sum>=(long)max*n){
            return sum/n;
        }
     
        //二分区间[0,max]
        int l=0,r=max;
        long ret=0;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(f2(batteries,n,mid)){
                l=mid+1;
                ret=mid;
            }
            else{
                r=mid-1;
            }
        }
        return ret;  
    }

}
